package com.asia.algorithmcode.dynamicProgram;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @DESCRIPTION: 119、杨辉三角2
 * @USER: wanfu
 * @DATE: 2025/5/22 星期四 14:23
 */
public class GetRow {

    public static void main(String[] args) {
        List<Integer> row = new GetRow().getRow(3);
        System.out.println();
    }


    public List<Integer> getRow(int rowIndex) {
        List<Integer> resList = new ArrayList<>();
        resList.add(1);

        for (int i = 1; i <= rowIndex; i++) {
            resList.add(0);
            for (int j = i; j > 0; j--) {
                resList.set(j, resList.get(j) + resList.get(j - 1));
            }
        }
        return resList;
    }


    /**
     * 优化了空间
     * @param rowIndex
     * @return
     */
//    public List<Integer> getRow(int rowIndex) {
//        List<Integer> preList = Arrays.asList(1);
//        List<Integer> resList = new ArrayList<>();
//        if (rowIndex == 0) {
//            return preList;
//        }
//
//        for (int i = 2; i <= rowIndex + 1; i++) {
//            resList = new ArrayList<>();
//            for (int j = 0; j < i; j++) {
//                if (j == 0 || j == i - 1) {
//                    resList.add(1);
//                } else {
//                    resList.add(preList.get(j - 1) + preList.get(j));
//                }
//            }
//            preList = resList;
//        }
//        return resList;
//    }

    /**
     * 空间复杂度太高
     * @param rowIndex
     * @return
     */
//    public List<Integer> getRow(int rowIndex) {
//        List<List<Integer>> resList = new ArrayList<>();
//        resList.add(Arrays.asList(1));
//        if (rowIndex == 0) {
//            return resList.get(resList.size() - 1);
//        }
//        for (int i = 2; i <= rowIndex+1; i++) {
//            List<Integer> list = new ArrayList<>();
//            for (int j = 0; j < i; j++) {
//                if (j == 0 || j == i - 1) {
//                    list.add(1);
//                } else {
//                    List<Integer> preList = resList.get(resList.size() - 1);
//                    list.add(preList.get(j - 1) + preList.get(j));
//                }
//            }
//            resList.add(list);
//        }
//        return  resList.get(resList.size() - 1);
//    }


}
